package Z.dailyExercise.March;

import java.util.HashMap;
import java.util.Map;
import java.util.TreeMap;

public class _剑指Offer63股票的最大利润 {

    /**
     * 双指针遍历--就是动态规划
     * 如果i大 则i++
     * 否则 更新最大利润
     * ==不应该从前后遍历
     * 准备min 和 结果数值 从前往后随时遍历
     * @param prices
     * @return
     */
    public int maxProfit(int[] prices) {
        int maxpro = 0,min= Integer.MAX_VALUE;
        for (int i = 0; i < prices.length; i++) {
            if (prices[i]<min){
                min = prices[i];
            }else {
                maxpro = Math.max(maxpro,prices[i]-min);
            }

        }
        return maxpro;
    }

    /**
     * 动态规划
     * dp[0]= 0
     */
    public int maxProfit1(int[] prices) {
        if (prices.length == 0){
            return 0;
        }
//        int[] dp = new int[prices.length];
//        dp[0] = 0;
//        int min = prices[0];
//
//        for (int i=1;i<prices.length;i++){
//            dp[i] = Math.max(dp[i-1],prices[i]-min);
//            min = Math.min(min,prices[i]);
//        }
//
//        return dp[prices.length-1];

        /**
         * 优化
         */

        int maxPro = 0;
        int min = Integer.MAX_VALUE;

        for (int num :prices){
            min = Math.min(num,min);
            maxPro = Math.max(maxPro,num-min);
        }

        return maxPro;


    }

}
